package leetcode.onehundred;

import java.util.Arrays;

//338. 比特位计数
public class CountBits {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits3(0)));
    }

    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = countOnes(i);
        }
        return res;
    }

    //x&=(x-1) 表示将二进制类型的x的最后一位1变为0
    private int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }


    //dp
    public int[] countBits2(int n) {
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            f[i] = f[i & (i - 1)] + 1;
        }
        return f;
    }

    //API
    public static int[] countBits3(int n) {

        int[] f = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            f[i] = Integer.bitCount(i);
        }
        return f;
    }

}
